package class04_归并排序.test;

/**
 * 左边比右边大两倍的数值
 */
public class Code04_BiggerThanRightTwice {
    public static int biggerTwice(int[] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int L, int R) {
        if(L == R){
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        int biggerTwice =  (process(arr, L, mid)
                + process(arr, mid + 1, R)
                + merge(arr, L, mid, R));
        return biggerTwice;
    }

    private static int merge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int size = help.length-1;
        int p1 = mid;
        int p2 = R;
        int biggerTwice = 0;

        int windowsR = mid + 1;
        for (int i = 0; i <= mid - L; i++) {
            while (windowsR <= R && arr[L + i] > arr[windowsR] * 2 ){
                windowsR ++;
            }
            biggerTwice += windowsR - mid - 1;
        }
        while (p1 >= L && mid < p2){
            help[size --] = arr[p1] > arr[p2]? arr[p1--] : arr[p2--];
        }
        while (p1 >= L){
            help[size --] = arr[p1--];
        }
        while (mid < p2){
            help[size --] = arr[p2--];
        }
        for (int i = 0; i < help.length; i++) {
            arr[i + L] = help[i];
        }
        return biggerTwice;
    }

    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generataRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if(biggerTwice(arr1) != comparator(arr2)){
                succeed = false;
                System.out.println( "arr1 = " + arr1.length +" arr2 = " + arr2.length);
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed?"Good!!":"Fuck!!");
    }

    private static void printArray(int[] arr1) {
        if(arr1 == null){
            return;
        }
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + " ");
        }
        System.out.println();
    }

    private static int comparator(int[] arr2) {
        if(arr2 == null || arr2.length < 2) {
            return 0;
        }
        int biggerTwice = 0;
        for (int i = arr2.length - 1; i >= 0 ; i--) {
            for (int j = 0; j < i; j++) {
                if(arr2[i]* 2 < arr2[j] ){
                    biggerTwice++;
                }
            }
        }
        return biggerTwice;
    }

    private static int[] copyArray(int[] arr1) {
        if(arr1 == null) {
            return new int[0];
        }
        int[] arr2 = new int[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr2[i] = arr1[i];
        }
        return arr2;
    }

    private static int[] generataRandomArray(int maxSize, int maxValue) {
        int size = (int)(Math.random() * (1 + maxSize));
        int[] arr2 = new int[size];
        for (int i = 0; i < size; i++) {
            arr2[i] = (int)(Math.random() * (1 + maxValue));
        }
        return arr2;
    }
}
